home *** CD-ROM | disk | FTP | other *** search
/ NetNews Offline 2 / NetNews Offline Volume 2.iso / news / comp / lang / c-part1 / 7080 < prev    next >
Encoding:
Internet Message Format  |  1996-08-05  |  2.3 KB

  1. Path: galaxy.ucr.edu!corsa!datadec
  2. From: datadec@corsa.ucr.edu (Kevin Marcus)
  3. Newsgroups: comp.lang.c
  4. Subject: Re: Finding a prime number
  5. Date: 18 Feb 1996 11:50:18 GMT
  6. Organization: UC Riverside, Dept. of Computer Science
  7. Message-ID: <4g73pq$h7j@galaxy.ucr.edu>
  8. References: <4fnnfuINNib7@keats.ugrad.cs.ubc.ca> <4fteet$b7e@sun001.spd.dsccc.com> <1996Feb16.180234.114184@kuhub.cc.ukans.edu>
  9. NNTP-Posting-Host: cs.ucr.edu
  10.  
  11. In article <1996Feb16.180234.114184@kuhub.cc.ukans.edu>,
  12.  <anh@kuhub.cc.ukans.edu> wrote:
  13. >
  14. >prime1*prime2*prim3*...*largest_prime_to_date + 1 ?
  15. >
  16. >I have not tried to see how long it would take to multiply a million or 
  17. >whatever the number of primes known is.
  18.  
  19. Actually, while multiplying them together would certainly take
  20. awhile, there is probably not enough disk space in the world to 
  21. hold such a number, either.
  22.  
  23. The largest prime number is certainly a mersenne prime , which was
  24. something like 2^853000ish - 1.  That number alone has roughly
  25. 300000 digits.  Imagine how many mor there are that are smaller than
  26. it.  
  27.  
  28. Better yet, while it slowly decreases, on average, 10% of the numbers
  29. from 1 - 10^1000000 are prime.  this means there are roughly 
  30. 10^999999 primes.  The average length of these primes? Only slightly less
  31. than 1 million digits.  As they say in atari land... Do the math!
  32.  
  33. BTW, this method of factoring has been known for some time.  One 
  34. variation on the above method is using factorials.  If it were
  35. possible to calculate a n factorial for large numbers instantly, and
  36. there were enough disk space to hold these results (taking the log
  37. of these numbers is no good since the precision of the log must
  38. be roughly equivalent to the size of the factorial anyways), then
  39. factoring could be done quickly using gcd (n, n-1!).
  40.  
  41. And, one again, unfortunately, it is not possible to use Sterlings
  42. eqn to produce this number, since even the best enhancements on
  43. Sterlings don't produce the exact factorial integer for long enough.
  44.  
  45. Instead, look at a way to represent factorials cheaply, and manipulate
  46. them simply.  You could be a rich person!
  47.  
  48. -- 
  49. Kevin Marcus:                            http://www.cs.ucr.edu/~datadec
  50.   CS Dept, U/CA, Riverside:              mailto:datadec@cs.ucr.edu
  51.   Virus-L archives:                      ftp://ftp.cs.ucr.edu/pub/virus-l
  52.   OKRA net.citizen Directory Services:   http://okra.ucr.edu/okra
  53.